#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef struct TreeNode 
{
	int val;
	struct TreeNode* left;
	struct TreeNode* right;
}BTNood;

BTNood* BuyNood(int x)
{
	BTNood* newnode = (BTNood*)malloc(sizeof(BTNood));
	if (newnode == NULL)
	{
		perror("malloc error");
		exit(-1);
	}
	newnode->right = newnode->left = NULL;
	newnode->val = x;
	return newnode;
}
Print(BTNood* root)
{
	printf("%d ", root->val);
	return Print(root->left) && Print(root->right);
}


int main()
{
	BTNood* n1 = BuyNood(4);
	BTNood* n2 = BuyNood(2);
	BTNood* n3 = BuyNood(7);
	BTNood* n4 = BuyNood(1);
	BTNood* n5 = BuyNood(3);
	BTNood* n6 = BuyNood(6);
	BTNood* n7 = BuyNood(9);

	n1->left = n2;
	n1->right = n3;
	n2->left = n4;
	n2->right = n5;
	n3->left = n6;
	n3->right = n7;
	Print(n1);
}


//翻转二叉树
//struct TreeNode* invertTree(struct TreeNode* root) {
//	if (root == NULL)
//		return NULL;
//	//用返回值接收，注意交换
//	struct TreeNode* left = invertTree(root->left);
//	struct TreeNode* right = invertTree(root->right);
//	root->left = right;
//	root->right = left;
//	return root;
//}

//相同的树
//bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
//	//解决子问题
//
//	//同时为空时
//	if (p == NULL && q == NULL)
//		return true;
//	//一个为空一个非空
//	if (p == NULL || q == NULL)
//		return false;
//	if (p->val != q->val)
//		return false;
//
//	return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
//}

//对称二叉树
// bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
//	//解决子问题
//
//
//	//同时为空时
//	if (p == NULL && q == NULL)
//		return true;
//	//一个为空一个非空
//	if (p == NULL || q == NULL)
//		return false;
//	if (p->val != q->val)
//		return false;
//	//对称左根右比，右跟左比
//	return isSameTree(p->left, q->right) && isSameTree(p->right, q->left);
//}
//bool isSymmetric(struct TreeNode* root) {
//	if (root == NULL)
//		return true;
//	return isSameTree(root->left, root->right);
//}

//另一棵树的子树
//bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
//	if (root == NULL)
//		return false;
//	if (root->val == subRoot->val)
//		if (isSameTree(root, subRoot))
//			return true;
//	return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
//}